\documentclass[11pt]{article} 

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{ctex}
\usepackage{url}

\addtolength{\textheight}{4.5cm}
\addtolength{\voffset}{-2.4cm}
\addtolength{\textwidth}{3.7cm}
\addtolength{\hoffset}{-2.2cm}   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% listings 是一个非常强大的 LaTeX 宏包，用于在文档中插入和格式化源代码。
%% 它提供了丰富的功能来高亮显示各种编程语言的语法，并且可以自定义代码的外观。
\usepackage{listings}
\usepackage{color}

% 设置列表的样式
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92} %背景颜色为淡土色
%\definecolor{backcolour}{rgb}{1,1,1} %背景颜色为白色

\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\ttfamily\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}

\lstset{style=mystyle}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{titling}
\setlength{\droptitle}{-2cm} %文档标题上移 

\title{高等代数实践作业（选做） - 程序计算辗转相除法}
\author{高等代数课程教学小组} 
%\date{2025年3月9日}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
使用R语言实现辗转相除法，计算两个多项式的最大公因式。
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{安装R语言}
\begin{enumerate}
\item  浏览R语言官网，了解开发团队、安装程序、使用文档、各种函数库和学术期刊等。\\
\url{https://www.r-project.org}
\item  上海交大镜像下载R程序并安装。 \\
\url{https://mirrors.sjtug.sjtu.edu.cn/cran/}
\item  下载实用数值计算包 pracma并安装。 \\ 
\url{https://mirrors.sjtug.sjtu.edu.cn/cran/web/packages/pracma/index.html}
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{例子}
在有理系数范围内，求下述两个多项式
\begin{eqnarray*}
 f(x) &=& x^4-2x^3-4x^2+4x-3, \\
 g(x) &=& 2x^3-5x^2-4x+3, 
\end{eqnarray*}
的最大公因式 $d(x)$, 并求 $u(x),v(x)$ 使得 $u(x)f(x) + v(x)g(x)=d(x)$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{例子解答}
\begin{enumerate}

\item  使用辗转相除法。为避免分式运算，先将被除式乘以适当的整数。
\begin{eqnarray}
 4 f(x) &=& q_1(x)g(x) + r_1(x), \label{eq-1}\\ 
 9 g(x) &=& q_2(x)r_1(x) + r_2(x), \label{eq-2}\\ 
 56 r_1(x) &=& q_3(x)r_2(x). \label{eq-3} 
\end{eqnarray}
这三个除法分别是 $4f(x)$ 除以 $g(x)$, 然后 $9g(x)$ 除以 $r_1(x)$, 最后 $56r_1(x)$ 除以 $r_2(x)$. 得到的商和余式分别为  
\begin{eqnarray*}
q_1(x) &=& 2x+1, \\
r_1(x) &=& -3x^2+14x-15, \\ 
q_2(x) &=& -6x-13, \\ 
r_2(x) &=& 56x-168, \\ 
q_3(x) &=& -3x+5, \\
r_3(x) &=& 0. 
\end{eqnarray*}

\item  因此 $f(x)$ 与 $g(x)$ 的最大公因式为 $d(x) = r_2(x) = 56x-168$. 

\item  这三次辗转相除的R语言代码：
\begin{lstlisting}[language=R]
library(pracma)f = c(1,-2,-4,4,-3) #输入多项式的系数g = c(2,-5,-4,3)res1 = polydiv(4*f,g) #辗转相除法q1 = res1$d #商r1 = res1$r #余式res2 = polydiv(9*g,r1) #辗转相除法q2 = res2$dr2 = res2$rres3 = polydiv(56*r1,r2) #辗转相除法q3 = res3$dr3 = res3$r\end{lstlisting}
这里用向量 $[1,-2,-4,4,-3]$ 表示多项式 $f(x)$, 用 polydiv 函数计算带余除法。

\item  从等式(\ref{eq-2})往回代，可得 
\begin{eqnarray*}
r_2(x) &=& 9g(x) - q_2(x)r_1(x) \\ 
&=& 9g(x) - q_2(x)[ 4f(x) - q_1(x)g(x) ] \\ 
&=& -4q_2(x)f(x) + [9+q_2(x)q_1(x)]g(x).
\end{eqnarray*}

\item  因此所求 $u, v$ 可以取为 
\begin{eqnarray*}
u(x) &=& -4q_2(x) = 24x+52, \\ 
v(x) &=& 9+q_2(x)q_1(x) =-12x^2-32x-4.
\end{eqnarray*}

\item  计算 $u,v$ 使得 $uf+vg=d$ 为 $f,g$ 的最大公因式 $d$ 的R语言代码：
\begin{lstlisting}[language=R]
u = -4*q2 #按回代公式计算u,vv = polyadd(c(9),polymul(q2,q1)) myd = polyadd(polymul(u,f),polymul(v,g)) #验证uf+vg=d 
\end{lstlisting}
这里用 polyadd 函数与 polymul 函数计算两个多项式的加法与乘法。

\item  如果写成 $(f(x),g(x))=d(x)$, 则默认要求 $d(x)$ 是首项系数为1的那个最大公因式，此时   
$$d(x) = \frac{1}{56}r_2(x) = x-3,$$
相应地可以取 
\begin{eqnarray*}
u(x) &=& \frac{1}{56}[-4q_2(x)] = \frac{3}{7}x+\frac{13}{14}, \\ 
v(x) &=& \frac{1}{56} [9+q_2(x)q_1(x) ] = -\frac{3}{14}x^2 - \frac{4}{7}x - \frac{1}{14}.
\end{eqnarray*}

\item  注：使得 $uf+vg=d$ 的 $u,v$ 不是唯一确定的。但是因为辗转相除法的计算路径是唯一的，所以通过上述算法得到的 $u,v$ 是唯一确定的。

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{习题}
\begin{enumerate}
\item 使用辗转相除法计算多项式 $f(x)=x^4+x^3-3x^2-4x-1$ 与 $g(x)=x^3+x^2-x-1$ 的最大公因式 $d(x)$. 并求多项式 $u(x)$ 与 $v(x)$ 使得 $d(x)=u(x)f(x)+v(x)g(x)$. 

\item  答案：最大公因式 $d(x)=-3x-3$. 使得 $uf+vg=d$ 的 $u,v$ 可取为
\begin{eqnarray*}
u(x) &=& 2x - 1, \\ 
v(x) &=& -2x^2 + x + 4.
\end{eqnarray*}
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}


